package huffman;

import java.io.ByteArrayOutputStream;

/**
 * Statistic node: value + count of occurrences, ordered by number of
 * occurrences, plus methods needed by encoder.
 */
class StatNode implements Comparable<StatNode>
{
	public static final StatNode NULL_NODE = null;
	
	private byte _value;
	private int _occurrences;
	private StatNode _left, _right;
	
	/** Starts with count = 1 */
	public StatNode(byte value)
	{
		_value = value; // avoid headaches
		_occurrences = 1;
		
		_left = null;
		_right = null;
	}

	/** Used for merging */
	public StatNode(StatNode left, StatNode right)
	{
		_occurrences = left._occurrences + right._occurrences;
		
		_left = left;
		_right = right;
	}
	
	public void increase()
	{
		_occurrences++;
	}
	
	public EncodedData encode(byte[] inputData)
	{
		BitPath[] encodingMap = new BitPath[256];
		recursiveCreateEncodingMap(encodingMap, new BitPath());
		
		BitOutputStream output = new BitOutputStream();
		int totBits = 0;
		
		for (byte b : inputData) {
			BitPath encodedBits = encodingMap[b & 0xFF];
			totBits += encodedBits.length();
			output.append(encodedBits);
		}

		return new EncodedData(output.toByteArray(), totBits, this);
	}
	
	public byte[] decode(byte[] inputData, int totBits)
	{
		BitInputStream input = new BitInputStream(inputData);
		ByteArrayOutputStream output = new ByteArrayOutputStream();
		
		for (int bitsUsed = 0; bitsUsed < totBits; )
		{
			bitsUsed = recursiveDecode(input, output, bitsUsed);
		}
		
		return output.toByteArray();
	}
	
	private int recursiveDecode(
			BitInputStream input, ByteArrayOutputStream output,
			int bitsUsed)
	{
		if (isLeaf()) {
			output.write(_value);
			return bitsUsed;
		}
		else {
			boolean nextBit = input.readNextBit();
			bitsUsed++;

			if (! nextBit) {
				return _left.recursiveDecode(input, output, bitsUsed);
			}
			else {
				return _right.recursiveDecode(input, output, bitsUsed);
			}
		}
	}

	/**
	 * Pre-order recursive addition to byte map.
	 * 
	 * @param encodingMap
	 *            filled with the values.
	 */
	private void recursiveCreateEncodingMap(
			BitPath[] encodingMap, BitPath bitPath)
	{
		if (isLeaf()) {
			encodingMap[_value & 0xFF] = new BitPath(bitPath); 
		}
		else {
			bitPath.append(false);
			_left.recursiveCreateEncodingMap(encodingMap, bitPath);
			bitPath.removeLast();
			
			bitPath.append(true);
			_right.recursiveCreateEncodingMap(encodingMap, bitPath);
			bitPath.removeLast();
		}
	}
	
	public boolean isLeaf()
	{
		 // one only it's ok too
		return _left == null && _right == null;
	}
	
	/** Compares by occurrences count. */
	@Override
	public int compareTo(StatNode o)
	{
		if (_occurrences < o._occurrences) return -1;
		else if (_occurrences == o._occurrences) return 0;
		else return 1;
	}
	
	@Override
	public String toString()
	{
		if (! isLeaf()) return "Internal";
		else return String.format("0x%02X: %s", _value, _occurrences);
	}
}